package _03LinkedList;

class _02SearchSinglyLinkedList {
    // Singly linked list node in Java
    class Node {
        int data;
        Node next;
        Node(int d) {
            data = d;
            next = null;
        }
    }
    Node head;

    // time complexity： O(1)
    // space complexity: O(1)
    // inserts a new node on the front of the list.
    public void push(int new_data) {
        // allocate new node
        Node new_node = new Node(new_data);

        // insert
        new_node.next = head;
        head = new_node;
    }

    // time complexity： O(n)
    // space complexity: O(1)
    // search a node
    public boolean search(int key) {
        Node cur = head;
        while(cur != null) {
            if(cur.data == key) return true;
            cur = cur.next;
        }
        return false;
    }

    public void printList() {
        Node temp = head;
        while(temp != null) {
            System.out.print(temp.data + " ");
            temp = temp.next;
        }
        System.out.println();
    }

    public static void main(String args[]) {

        _02SearchSinglyLinkedList list = new _02SearchSinglyLinkedList();

        list.push(3);
        list.push(9);
        list.push(5);
        list.push(8);
        list.push(2);
        System.out.print("Linked List: ");
        list.printList();

        System.out.println("Search node's data(8): " + list.search(2));
    }
}